

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

The Sliding Puzzle

The picture above shows an instance of the $3 \times 3$ sliding puzzle: There is a board of size $3 \times 3$ with 8 tiles on it. These tiles are numbered with digits from the set $\{1,\cdots, 8\}$. As the the $3 \times 3$ board has an area of $9$ but there are only $8$ tiles, there is an empty square on the board. Tiles adjacent to the empty square can be moved into the square, thereby emptying the space that was previously occupied by theses tiles. The goal of the $3 \times 3$ puzzle is to transform the state shown on the left of the picture above into the state shown on the right. We represent states as tuples of tuples. For example, the state shown above on the left side is represented as the following tuple:

        ( (8, 0, 6),
          (5, 4, 7),
          (2, 3, 1)
        )

If we represent states this way, given a state s, the expression s[row][col] returns the tile in the specified row and col.

In order to get an idea of the sliding puzzle, you can play it online at http://mypuzzle.org/sliding.

The function call find_tile(tile, State) finds the coordinates of the given tile in State. The tile is represented as a number from the set $\{0,1,\cdots,8\}$, where $0$ represents the empty tile. The parameter State is a tuple of tuples that specifies the positions of the tiles. If (row, col) is the result returned by find_tile, then we have:

    State[row][col] == tile



In [ ]:

    
def find_tile(tile, State):
    n = len(State)
    for row in range(n):
        for col in range(n):
            if State[row][col] == tile:
                return row, col

Since breadth first search stores the set of states that have been visited, we have to represent states by immutable objects and hence we represent the states as tuples of tuples. In order to be able to change these states, we have to transform these tuples of tuples into lists of lists.
The function to_list transforms a tuple of tuples into a list of lists.



In [ ]:

    
to_list = lambda State: [list(row) for row in State]

The function to_tuple transforms a list of lists into a tuple of tuples.



In [ ]:

    
to_tuple = lambda State: tuple(tuple(row) for row in State)

Given a State that satisfies

    State[row][col] == 0

and a direction (dx, dy) that is an element form the set $\bigl\{ (1, 0), (-1, 0), (0, 1), (0, -1) \bigr\}$, the function move_dir moves the empty tile in the direction (dx, dy).



In [ ]:

    
def move_dir(State, row, col, dx, dy):
    State = to_list(State)
    State[row     ][col     ] = State[row + dx][col + dy]
    State[row + dx][col + dy] = 0
    return to_tuple(State)

Given a State of the sliding puzzle, the function next_states(State) computes all those states that can be reached from State in one step.



In [ ]:

    
def next_states(State):
    n          = len(State)
    row, col   = find_tile(0, State)
    New_States = set()
    Directions = [ (1, 0), (-1, 0), (0, 1), (0, -1) ]
    for dx, dy in Directions:
        if row + dx in range(n) and col + dy in range(n):
            New_States.add(move_dir(State, row, col, dx, dy))
    return New_States

Below, we have defined the start state, which is the state shown in the figure above on the left.



In [ ]:

    
start = ( (8, 0, 6),
          (5, 4, 7),
          (2, 3, 1)
        )



In [ ]:

    
next_states(start)



In [ ]:

    
goal = ( (0, 1, 2), 
         (3, 4, 5), 
         (6, 7, 8)
       )

Below is an instance of the $4 \times 4$ puzzle that can be solved in 40 steps.



In [ ]:

    
start2 = ( (  0,  1,  2,  3 ),
           (  4,  5,  6,  8 ),
           ( 14,  7, 11, 10 ),
           (  9, 15, 12, 13 )
         )
goal2  = ( (  0,  1,  2,  3 ),
           (  4,  5,  6,  7 ),
           (  8,  9, 10, 11 ),
           ( 12, 13, 14, 15 )
         )

For informed search we need to implement a heuristic that estimates to distance between two states. The function manhattan implemented below takes as argument two states of the sliding puzzle and computes the Manhattan distance between these states. Basically, the manhattan distance measure the number of moves that it would take to transform stateA into stateB if we were allowed to slide different tiles on top of each other.



In [ ]:

    
def manhattan(stateA, stateB):
    n = len(stateA)
    result = 0
    for rowA in range(n):
        for colA in range(n): 
            tile = stateA[rowA][colA]
            if tile != 0:
                rowB, colB = find_tile(tile, stateB)
                result += abs(rowA - rowB) + abs(colA - colB)
    return result



In [ ]:

    
manhattan(start, goal)

Animation

The package ipycanvas, which is imported below, can be installed using the following command:

    conda install -c conda-forge ipycanvas

This package is useful for drawings and animations. Its documentation can be found at: https://ipycanvas.readthedocs.io/en/latest/.



In [ ]:

    
import ipycanvas as cnv

The module time is part of the standard library so it is preinstalled. We have imported it because we need the function time.sleep(secs) to pause the animation for a specified time.



In [ ]:

    
import time

The global variable Colors specifies the colors of the tiles.



In [ ]:

    
Colors = ['white', 'lightblue', 'pink', 'magenta', 'orange', 'red', 'yellow', 'lightgreen', 'gold',
          'CornFlowerBlue', 'Coral', 'Cyan', 'orchid', 'DarkSalmon', 'DeepPink', 'green'
         ]

The global variable size specifies the size of one tile in pixels.



In [ ]:

    
size = 100

The function draw(State, canvas, dx, dy, tile, x) draws a given State of the sliding puzzle, where tile has been moved by offset pixels into the direction (dx, dy).



In [ ]:

    
def draw(State, canvas, dx, dy, tile, offset):
    canvas.text_align    = 'center'
    canvas.text_baseline = 'middle'
    with cnv.hold_canvas(canvas):
        canvas.clear()
        n = len(State)
        for row in range(n):
            for col in range(n):
                tile_to_draw = State[row][col]
                color = Colors[tile_to_draw]
                canvas.fill_style = color
                if tile_to_draw not in (0, tile):
                    x = col * size
                    y = row * size
                    canvas.fill_rect(x, y, size, size)
                    canvas.line_width = 3.0
                    x += size // 2
                    y += size // 2
                    canvas.stroke_text(str(tile_to_draw), x, y)
                elif tile_to_draw == tile:
                    x = col * size + offset * dx
                    y = row * size + offset * dy
                    canvas.fill_rect(x, y, size, size)
                    canvas.line_width = 3.0
                    x += size // 2
                    y += size // 2
                    if tile_to_draw != 0:
                        canvas.stroke_text(str(tile_to_draw), x, y)



In [ ]:

    
def create_canvas(n): 
    canvas = cnv.Canvas(size=(size * n, size * n))
    canvas.font = '100px serif'
    return canvas

The global variable delay controls the speed of the animation.



In [ ]:

    
delay = 0.002

The function call tile_and_direction(state, next_state) takes a state and the state that follows this state and returns a triple (tile, dx, dy) where tileis the tile that is moved to transform state into next_state and (dx, dy) is the direction in which this tile is moved.



In [ ]:

    
def tile_and_direction(state, next_state):
    row0, col0 = find_tile(0, state)
    row1, col1 = find_tile(0, next_state)
    return state[row1][col1], col0-col1, row0-row1

Given a list of states representing a solution to the sliding puzzle, the function call animation(Solution) animates the solution.



In [ ]:

    
def animation(Solution):
    start = Solution[0]
    n = len(start)
    canvas = create_canvas(n)
    draw(start, canvas, 0, 0, 0, 0)
    m = len(Solution)
    display(canvas)
    for i in range(m-1):
        state = Solution[i]
        tile, dx, dy = tile_and_direction(state, Solution[i+1])
        for offset in range(size+1):
            draw(state, canvas, dx, dy, tile, offset)
            time.sleep(delay)



In [ ]: